package heap;

import java.util.*;
/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 王圆豪
 * Date: 2024-10-07
 * Time: 21:34
 */
public class Heap<E extends Comparable<E>> {
    private E[] elem;
    private int usedSize;

    public E[] getElem() {
        return elem;
    }

    public void setElem(E[] elem) {
        this.elem = elem;
    }

    public Heap(E[] elem) {
        this.elem = elem;
        this.usedSize = elem.length;
    }

    //创建小根堆
    public void createHeap(E[] elem){
        int root = (usedSize - 2) / 2;
        while (root >= 0){
            downSift(root, elem);
            root--;
        }
    }

    //交换元素
    public void swap(E[] arr, int i, int j){
        E tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    //删除堆顶元素
    public void delete(){
        swap(elem, 0, usedSize - 1);
        usedSize--;
        downSift(0, elem);
    }

    //向下调整
    private void downSift(int parent, E[] elem) {
        int child1 = parent * 2 + 1;
        while (child1 < usedSize) {
            int child2 = child1 + 1;
            if (elem[child1].compareTo(elem[parent]) < 0){
                if (child2 < usedSize && elem[child2].compareTo(elem[child1]) < 0){
                    swap(elem, parent, child2);
                    parent = child2;
                }else {
                    swap(elem, parent, child1);
                    parent = child1;
                }
            }else {
                if (child2 < usedSize && elem[child2].compareTo(elem[parent]) < 0){
                    swap(elem, parent, child2);
                    parent = child2;
                }else {
                    parent = child1;
                }
            }
            child1 = parent * 2 + 1;
        }
    }

    //是否 满
    private boolean isFull() {
        return usedSize == elem.length;
    }
    //插入数据
    public void add(E val){
        if(isFull()){
            elem = Arrays.copyOf(elem, 2 * usedSize);
        }
        elem[usedSize++] = val;
        upSift(elem, usedSize - 1);
    }

    //向上调整
    private void upSift(E[] elem, int child) {
        int parent = (child - 1) / 2;

        while (parent >= 0){
            if (elem[parent].compareTo(elem[child]) > 0){
                swap(elem, parent, child);
                child = parent;
                parent = (child - 1) / 2;
            }else {
                break;
            }
        }
    }
}
